#include "headfiles.h"

using namespace std;

NODE *createLinkedList(const char *file_name) {
    if (file_name == NULL) {
        return NULL;
    }

    fstream fs;
    fs.open(file_name, iostream::in);
    if (!fs.is_open()) {
        return NULL;
    }

    NODE *head, *tail, *node;
    head = NULL;
    string str;
    while (fs >> str) {
        if (str.empty()) {
            break;
        }

        int val = atoi(str.c_str());

        node = new NODE;
        memset(node, 0, sizeof(NODE));
        node->val = val;

        if (head == NULL) {
            tail = node;
        }

        node->next = head;
        head = node;
    }

    if (tail) {
        tail->next = head;
    }

    return head;
}

// If the head is changed, return the new head pointer
// Otherwise, return the head itself
NODE * cycleLinkedListInsertion(NODE *head, int x) {
    NODE *node = (NODE *)malloc(sizeof(NODE));
    memset(node, 0, sizeof(NODE));
    node->val = x;
    
    // Find the location where x should be inserted
    NODE *pre, *cur, *next;
    // empty linked list, create a new node
    if (head == NULL) {
        node->next = node;
        return node;
    }

    // x is bigger than the curren node
    // traverse back to the start
    cur = head;
    if (cur->val > x) {
        pre = cur;
        cur = cur->next;
        while (pre->val <= cur->val) {
            pre = cur;
            cur = cur->next;

            // All nodes are of the same value
            if (cur == head) {
                break;
            }
        }
    }

    while (cur->val < x) {
        pre = cur;
        cur = cur->next;
        
        // hit the head of the linked list
        if (pre->val > cur->val) {
            break;
        }

        // all values are the same, and x is biggest one
        if (cur == head) {
            break;
        }
    }

    pre->next = node;
    node->next = cur;

    return head;
}

void printCycleLinkedList(NODE *head) {
    NODE *n = head;
    while (n) {
        cout << n->val << "\t";
        n = n->next;
        if (n == head) {
            break;
        }
    }
    cout << endl;

    return;
}

void destroyCycleLinkedList(NODE *head) {
    NODE *n = head;
    NODE *tmp;
    while (n) {
        tmp = n->next;
        free(n);

        if (tmp == head) {
            break;
        }
        n = tmp;
    }

    return;
}
